package ACWing.SearchAndGraphTheory.最短路;
//850. Dijkstra求最短路 II

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
//堆优化及可以用堆的特性可以找出当前权值最小的一个节点
/**
 * @author :chenjie
 * @date :Created 2022/12/27 16:13
 */
public class Dijkstra2 {
    static int n , m , N = 1000010;
    static PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->{return a[1] - b[1];});//堆
    static int[] dist = new int[N];//距离数组
    static boolean[] f = new boolean[N];//标记数组
    static int[] h = new int[N], ne = new int[N], e = new int[N], w = new int[N];//邻接表
    static int idx ;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        Arrays.fill(h,-1);
        for (int i = 0; i < m; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            add(a,b,c);
        }
        System.out.println(Dijkstra());
    }
    static int Dijkstra(){
        Arrays.fill(dist,0x3f3f3f3f);//初始化数组使其达到无穷大
        dist[1]=0;
        q.offer(new int[]{1,0});//初始化堆中的元素
        while (q.size()!=0){//类似与bfs
            int[] poll = q.poll();
            int t=poll[0];
            int distmin=poll[1];
            if(f[t]){
                continue;
            }
            f[t]=true;
            for (int i = h[t]; i != -1; i=ne[i]) {
                int j=e[i];
                if(dist[j]>distmin+w[i]){//如果存储的距离大小大于本节点到j节点的距离的话更新
                    dist[j]=distmin+w[i];
                    q.offer(new int[]{j,dist[j]});//将这个节点存储进去排序
                }
            }
        }
        if(dist[n]==0x3f3f3f3f){
            return -1;
        }else {
            return dist[n];
        }
    }
    public static void add(int a,int b,int c){
        e[idx]=b;
        ne[idx]=h[a];
        w[idx]=c;//存储到b的权值
        h[a]=idx++;
    }
}
